The design process for many integrated circuits (“chips”) typically contains a number of well known sequential operations. Initially, the proposed functionality of a circuit is analyzed by one or more chip designers. These designers then use design capture tools-to enter the logical components of the circuit and their interactions. This step involves generating a description of the logic design to be implemented on the circuit chip in an appropriate machine-readable form. One of the commonly used methods for specifying a design is a hardware description language (HDL). This language contains specific functions and syntax to allow complex hardware structures to be described in a compact and efficient way. Computer-aided design tools are available to compile the HDL description specifying the design into lower forms of description. The output of the design tools is a logic design database which completely specifies the logical and functional relationships among the components of the design.
The logic design database is then passed as input to a layout tool, which typically includes a placement tool (placer) and a routing tool (router). Placement is the process whereby each component (or design object) of the design is allocated to a physical position on the chip. The aim of the placer is to place connected design objects in close physical proximity to one another. This conserves space on the chip and increases the probability that the desired interconnections will be successfully completed by the router. Additionally, the performance of the circuit may be improved because excess capacitance and resistance caused by long interconnect paths between design objects will slow down the circuit and, in certain cases, delay critical signals and possibly cause functional failures. Placement may take place either manually or automatically, or in combination. If placement is done manually, a chip designer interacts with a placement tool to define the location on the chip where each design object is to be placed. Automatic placement relies on sophisticated algorithms to place the design objects on the chip without the need for human intervention. As circuits get more complex and device geometry becomes sub-micron, it is rapidly becoming extremely difficult for a human chip designer to manage the complexity of the placement and routing operations. For example, modern designs contain tens of thousands of design objects, making the time needed for complete manual placement prohibitive.
After placement is complete, a routing step is performed. The purpose of routing is to connect the pins in each net of a logic design. A net is a collection of pins that must be connected together electrically by the router. A net may have one or more driver pins and one or more load pins. The driver pins on a net are the source of electrical signals that are fed to the load pins through an interconnection path chosen by the router. The position of the pins in any particular net are decided by the placement process. Routing determines exactly the interconnection paths between driver and load pins on a net. The routing problem can be significantly reduced in complexity if a near-optimal placement of the design objects has been achieved.
After placement and routing, it is often necessary to verify that the design functions in ways expected by the designer. This verification may be achieved by simulation. During post-layout verification, the operation of the logic design is examined. After routing, the precise resistances and capacitances of a design's interconnections are known and consequently, post-layout tools have an accurate picture of the actual circuit in the time domain. The post-layout verification, masks and test patterns are typically generated for use in manufacturing and testing the circuit.
The design tools involved in the CAD flow that are used for verification and mapping an HDL circuit into a routed circuit are commonly implemented in software executing on an engineering workstation.
It can be seen from the above that placement has an important effect on the CAD process. Thus, it is desirable to generate a placement solution that is as optimal as possible. Recently, it has been found that layout may be improved by making incremental modifications to a fully placed and/or fully routed design. Several incremental placement tools (incremental placers) have been proposed. In one approach, placement changes are made based on a characterization of a routed design. Specifically, the coupling capacitance of the routed design is measured in each placement region and these measurements are used to help estimate the effect that incremental placement changes will have on delay. Additionally, the algorithm attempts to account for the effect of placement changes on the structure of routes. The placement problem is formulated analytically as a system of equations to be solved. An example of this approach is described in C. Changfan, Y-C Hsu, and F-S Tsai, “Timing Optimization on Routed Designs with Incremental Placement and Routing Characterization,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 19, No. 2, February 2000, pp. 188-196.
A second approach uses an analytical formulation with an objective function that aims to maximize the difference between required delay and actual delay on the critical paths of a routed design. One unique feature of this formulation is that it not only computes a new placement for objects on the circuit's critical path, it also determines a new placement for the Steiner points in the routing of crictical path connections. Steiner points are branch points in the routing of a net. For example, consider a net with one driver pin and two load pins, A and B. Assume we first route the connection between the driver and load A. Then, when we route to load B, we may branch off the routing path between the driver and load A. The point at which we choose to branch off is referred to as a Steiner point. Returning to the incremental placement approach, constraints are added to the formulation to avoid overly increasing the delay of near-critical paths. The incremental placement algorithm can be used within a loop which attempts to improve several critical paths in each loop iteration. An example of this approach is described in A. Ajami and M. Pedram, “Post-Layout Timing-Driven Cell Placement Using an Accurate Net Length Model with Movable Steiner Points,” ASIA South Pacific DAC, 2001, pp. 595-600.
In both of the incremental placers described above, delay is computed using the “Elmore” delay model. In the Elmore model, delay between two connected objects is a continuous function of the distance between the objects. This is because wire resistance and capacitance are determined based on distance and technology-specific parameters. Therefore these placers are more suited to ASIC technology and less suitable for FPGA technology. This is because FPGAs have pre-fabricated routing resources of specific discrete lengths, which generally makes it very difficult to find a continuous function relating delay to distance.
In a third approach to incremental placement, the placement area is divided into regions and a local improvement strategy is employed in each region. The design objects placed in a region are rearranged taking delays, timing criticality and wirelength into account. The local placement task is formulated as a max-flow min-cost problem. Each region is improved sequentially and after covering the entire placement area, the regions may be redefined and the process repeated. One disadvantage of this method is that it does not consider the global placement problem—it only considers placement changes within a local placement region. An example of this approach is described in K. Doll, F. M. Johannes, and K. J. Antreich, “Iterative Placement Improvement by Network Flow Methods,” IEEE Trans. on Computer-Aided Design of Integrated Circuits, Vol. CAD-13, October 1994, pp. 1190-1200.